package com.test.leeCode;

/**
 * @author sunhl
 * @Description: 力扣第 21 题「合并两个有序链表」 核心代码模式
 * 所属章节: 第零章: 双指针技巧秒杀七道链表题目
 * @Date: created in 2025/1/10 星期五 23:54
 * @Modified By:
 */
public class T21_MergeTwoSortedLinkedLists {
    private class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 虚拟头结点
        // 何时使用虚拟头结点
        //
        // 什么时候需要用虚拟头结点？
        // 总结下：当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。
        ListNode dummy = new ListNode(-1), p = dummy;
        ListNode p1 = l1, p2 = l2;

        while (p1 != null && p2 != null) {
            // 比较 p1 和 p2 两个指针
            // 将值较小的的节点接到 p 指针
            if (p1.val > p2.val) {
                p.next = p2;
                p2 = p2.next;
            } else {
                p.next = p1;
                p1 = p1.next;
            }
            // p 指针不断前进
            p = p.next;
        }

        if (p1 != null) {
            p.next = p1;
        }

        if (p2 != null) {
            p.next = p2;
        }

        return dummy.next;
    }
}
